
// https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2/

/*
我们在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：

如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；也就是说，我们把原问题缩小成了一个规模为 (K-1, i-1) 的子问题；

如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼；也就是说，我们把原问题缩小成了一个规模为 (K, N-i) 的子问题；

这样一来，我们定义 dp(K, N)dp(K,N) 为在状态 (K, N)(K,N) 下最少需要的步数。根据以上分析我们可以列出状态转移方程：
    dp(K,N) = 1 + min(max(dp(K−1, i-1), dp(K,N−i)))

    上面的是假设，实际并不知道坏没坏，故需要覆盖全面的话，需要获取最大步数，即：max(dp(K-1, i-1), dp(K, N-i) )+ 1

必须保证 【鸡蛋碎了之后接下来需要的步数】 和 【鸡蛋没碎之后接下来需要的步数】 二者的 最大值 最小，这样就保证了在最坏情况下 dp(K, N) 的值最小。。

*/


/*
def superEggDrop(K: int, N: int):

    memo = dict()
    def dp(K, N) -> int:
        # base case
        if K == 1: return N
        if N == 0: return 0
        # 避免重复计算
        if (K, N) in memo:
            return memo[(K, N)]

        res = float('INF')
        # 穷举所有可能的选择
        for i in range(1, N + 1):
            res = min(res,
                max(
                    dp(K, N - i),
                    dp(K - 1, i - 1)
                ) + 1
            )
        # 记入备忘录
        memo[(K, N)] = res
        return res

    return dp(K, N)
*/

<!--class Solution {
    int[][] dp;
    public int superEggDrop(int K, int N)
    {
        dp = new int[K+1][N+1];
        return getDp(K, N);
    }

    public int getDp(int K, int N)
    {
        // 当鸡蛋数K为 1 时，显然只能线性扫描所有楼层
        if (K == 1) return N;

        // 当楼层数N等于 0 时，显然不需要扔鸡蛋
        if (N == 0) return 0;

        if (dp[K][N] != 0){
            return dp[K][N];
        } else {
            int res = Integer.MAX_VALUE;

            // 随机从楼层中选择一层楼抛【只需要关心在楼列表中排第几，不需要关心真正的层号，因为每一次跟层号无关，极端情况下，每一层都是需要遍历的（第一个鸡蛋碎了）】
            // 这里for 是为了获得不同楼层抛出的最优解
            for (int i=1; i<N+1; i++){
                res = Math.min(res, Math.max(getDp(K, N-i), getDp(K-1, i-1))+1);
            }

            dp[K][N] = res;
            return res;
        }
    }
}-->
<?php
class Solution {
    public static $memo = array();
    /**
     * @param Integer $K
     * @param Integer $N
     * @return Integer
     */
    function superEggDrop($K, $N) {
        return self::dp($K, $N);
    }

    /**
     * @param $K 剩下的鸡蛋数量
     * @param $N 剩余的楼层数量
     * @return int|mixed
     */
    static function dp($K, $N) {
        if (isset(self::$memo[$K][$N])) {
            return self::$memo[$K][$N];
        }

        // 当剩下的鸡蛋数K为 1 时，显然只能线性扫描所有楼层
        if ($K == 1) {
            self::$memo[$K][$N] = $N;
            return $N;
        }

        // 当剩下的楼层数N等于 0 时，显然不需要扔鸡蛋
        if ($N == 0) {
            self::$memo[$K][$N] = 0;
            return 0;
        }

        $res = PHP_INT_MAX;
        // 随机从楼层中选择一层楼抛【只需要关心在楼列表中排第几，不需要关心真正的层号，因为每一次跟层号无关，极端情况下，每一层都是需要遍历的（第一个鸡蛋碎了）】
        // 这里for 是为了获得不同楼层抛出的最优解
        for ($i=1; $i<=$N; $i++) {
            $res = min($res, max(self::dp($K-1, $i-1), self::dp($K, $N-$i))+1);
        }

        self::$memo[$K][$N] = $res;
        return $res;
    }
}
// https://my.oschina.net/u/4406332/blog/3233417